import numpy as np
from typing import List, Tuple
class KMeans:
    def __init__(self, k: int, max_iterations: int = 100):
        self.k = k
        self.max_iterations = max_iterations
        self.centroids = None
    def fit(self, X: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
        """ 执行K-means聚类 """
        # 随机选择初始质心
        self.centroids = X[np.random.choice(X.shape[0], self.k, replace = False)]
        for _ in range(self.max_iterations):
            # 分配每个点到最近的质心
            labels = self._assign_clusters(X)
            # 更新质心
            new_centroids = self._update_centroids(X, labels)
            # 如果质心没有变化，算法收敛
            if np.all(self.centroids == new_centroids):
                break
            self.centroids = new_centroids
        return self.centroids, labels
    def _assign_clusters(self, X: np.ndarray) -> np.ndarray:
        """ 将数据点分配到最近的质心 """
        distances = np.sqrt(((X - self.centroids[:, np.newaxis]) ** 2).sum(axis = 2))
        return np.argmin(distances, axis = 0)
    def _update_centroids(self, X: np.ndarray, labels: np.ndarray) -> np.ndarray:
        """ 计算新的质心 """
        new_centroids = np.array([X[labels == k].mean(axis = 0) for k in range(self.k)])
        return new_centroids
    def predict(self, X: np.ndarray) -> np.ndarray:
        """ 预测新数据点属于哪个簇 """
        return self._assign_clusters(X)
# 示例数据集
X = np.array([
    [1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11],
    [1.2, 1.9], [7, 9], [4, 6], [2, 3], [2.5, 2.9], [9.5, 10]
])
# 运行K-means算法
kmeans = KMeans(k = 3)
centroids, labels = kmeans.fit(X)
# 输出结果
print("质心:")
print(centroids)
print("\n每个点的簇标签:")
for point, label in zip(X, labels):
    print(f"点 {point} 属于簇 {label}")
